λ¬Έμ
0λΆν° NκΉμ§μ μ μ Kκ°λ₯Ό λν΄μ κ·Έ ν©μ΄ Nμ΄ λλ κ²½μ°μ μλ₯Ό ꡬνλ νλ‘κ·Έλ¨μ μμ±νμμ€.
λ§μ μ μμκ° λ°λ κ²½μ°λ λ€λ₯Έ κ²½μ°λ‘ μΌλ€(1+2μ 2+1μ μλ‘ λ€λ₯Έ κ²½μ°). λν ν κ°μ μλ₯Ό μ¬λ¬ λ² μΈ μλ μλ€.
μ λ ₯
- 첫째 μ€μ λ μ μ N(1 β€ N β€ 200), K(1 β€ K β€ 200)κ° μ£Όμ΄μ§λ€.
μΆλ ₯
- 첫째 μ€μ λ΅μ 1,000,000,000μΌλ‘ λλ λλ¨Έμ§λ₯Ό μΆλ ₯νλ€.
π Logic
for (int i=0; i<201 ;i++) {
dp[i][0] = 1;
dp[1][i] = 1;
}
for (int i=0;i<=N;i++)
dp[2][i] = i+1;
- dp λ°°μ΄ μ΄κΈ°ν
- iκ°μ μ μλ‘ jλ₯Ό λ§λλ κ²½μ°μ μκ° dp[i][j]μ μ μ₯
for (int i=3;i<=K;i++) {
for (int j=1;j<=N;j++) {
for (int k=0;k<=j;k++) {
dp[i][j] += dp[i-1][k]%1000000000;
}
}
}
- μ νμμ μλ₯Ό λ€μ΄, dp[3][1]μ ꡬνλ κ²½μ°, μ¦ 3κ°μ μ μλ‘ 1μ λ§λ€μ΄μΌ νλ κ²½μ°μ μλ dp[2][0] + dp[2][1]λ‘, 2κ°μ μ μλ‘ 0μ λ§λλ κ²½μ°μ μμ 2κ°μ μ μλ‘ 1μ λ§λλ κ²½μ°μ μλ₯Ό λνλ©΄ λλ€
- λ°λΌμ, dp[i][j] = dp[i-1][0] + ... + dp[i-1][j]κ° λλ€
π CODE
μ½λ 보기/μ κΈ°π«
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static long dp[][] = new long[201][201];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String tc = br.readLine();
StringTokenizer st = new StringTokenizer(tc, " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
for (int i=0; i<201 ;i++) {
dp[i][0] = 1;
dp[1][i] = 1;
}
for (int i=0;i<=N;i++)
dp[2][i] = i+1;
for (int i=3;i<=K;i++) {
for (int j=1;j<=N;j++) {
for (int k=0;k<=j;k++) {
dp[i][j] += dp[i-1][k]%1000000000;
}
}
}
System.out.println(dp[K][N]%1000000000);
}
}
βοΈ Review
- μ€λλ§μ μκ³ λ¬Έμ λ₯Ό νΈλ ν°λΌ μμ΄λμ΄λ₯Ό μ‘λλ° νμ°Έ κ±Έλ Έλ κ² κ°λ€
- λ§μ μ νμμ λμΆν΄λ΄λ©΄ μ¬μ΄ λ¬Έμ μμ§λ§ μ νμ λμΆμ΄ μ΄λ €μ κ³ , μ²μμΌλ‘ javaλ‘ νΌ λ¬Έμ μ¬μ λΈλ‘κ·Έλ₯Ό μ°Έκ³ νλ€